/*-------------------------------------------------------------------------
 *
 * nbtsplitloc.c
 *	  Postgres btree 实现的选择拆分点代码。
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *	  src/backend/access/nbtree/nbtsplitloc.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "access/nbtree.h"
#include "storage/lmgr.h"

typedef enum
{
	/* 搜索物化分割点列表的策略 */
	SPLIT_DEFAULT,				/* 给截断一些权重 */
	SPLIT_MANY_DUPLICATES,		/* 找到最小区分点 */
	SPLIT_SINGLE_VALUE			/* 左页几乎满 */
} FindSplitStrat;

typedef struct
{
	/* 分割留下的空闲空间的细节 */
	int16		curdelta;		/* 当前的左空/右空差值 */
	int16		leftfree;		/* 分割后左页的空闲空间 */
	int16		rightfree;		/* 分割后右页的空闲空间 */

	/* 分割点标识字段（由_bt_findsplitloc返回） */
	OffsetNumber firstrightoff; /* 右页上的第一个原始页面项 */
	bool		newitemonleft;	/* 新项放在左边，还是右边？ */
} SplitPoint;

typedef struct
{
	/* _bt_recsplitloc的上下文数据 */
	Relation	rel;			/* 索引关系 */
	Page		origpage;		/* 正在进行分割的页面 */
	IndexTuple	newitem;		/* 新项（导致页面分割） */
	Size		newitemsz;		/* 新项的大小（包括行指针） */
	bool		is_leaf;		/* 如果正在分割叶页则为T */
	bool		is_rightmost;	/* 如果正在分割层级上的最右页面则为T */
	OffsetNumber newitemoff;	/* 新项要插入的位置 */
	int			leftspace;		/* 左页上可用的空间 */
	int			rightspace;		/* 右页上可用的空间 */
	int			olddataitemstotal;	/* 旧项占用的空间 */
	Size		minfirstrightsz;	/* 最小的首次右侧大小 */

	/* 候选分割点数据 */
	int			maxsplits;		/* 最大分割次数 */
	int			nsplits;		/* 当前分割次数 */
	SplitPoint *splits;			/* 页面上的所有候选分割点 */
	int			interval;		/* 当前可接受的分割点范围 */
} FindSplitData;

static void fc__bt_recsplitloc(FindSplitData *fc_state,
							OffsetNumber fc_firstrightoff, bool fc_newitemonleft,
							int fc_olddataitemstoleft,
							Size fc_firstrightofforigpagetuplesz);
static void fc__bt_deltasortsplits(FindSplitData *fc_state, double fc_fillfactormult,
								bool fc_usemult);
static int	fc__bt_splitcmp(const void *fc_arg1, const void *fc_arg2);
static bool fc__bt_afternewitemoff(FindSplitData *fc_state, OffsetNumber fc_maxoff,
								int fc_leaffillfactor, bool *fc_usemult);
static bool fc__bt_adjacenthtid(ItemPointer fc_lowhtid, ItemPointer fc_highhtid);
static OffsetNumber fc__bt_bestsplitloc(FindSplitData *fc_state, int fc_perfectpenalty,
									 bool *fc_newitemonleft, FindSplitStrat fc_strategy);
static int	fc__bt_defaultinterval(FindSplitData *fc_state);
static int	fc__bt_strategy(FindSplitData *fc_state, SplitPoint *fc_leftpage,
						 SplitPoint *fc_rightpage, FindSplitStrat *fc_strategy);
static void fc__bt_interval_edges(FindSplitData *fc_state,
							   SplitPoint **fc_leftinterval, SplitPoint **fc_rightinterval);
static inline int fc__bt_split_penalty(FindSplitData *fc_state, SplitPoint *fc_split);
static inline IndexTuple fc__bt_split_lastleft(FindSplitData *fc_state,
											SplitPoint *fc_split);
static inline IndexTuple fc__bt_split_firstright(FindSplitData *fc_state,
											  SplitPoint *fc_split);


/*
 * _bt_findsplitloc() -- 找到一个合适的位置来拆分页面。
 *
 * 这里的主要目标是使每个拆分页面上的自由空间相等，*在考虑插入的元组*之后。  （如果我们未能考虑到它，我们可能会发现页面中可用空间不足！）
 *
 * 如果页面是其级别上最右边的页面，我们就尝试安排将左侧拆分页面填充至 fillfactor% 满。  这样，当我们插入依次递增的键时（考虑序列、时间戳等），我们将得到一个页面大约填充 fillfactor% 的树，而不是没有这个特殊情况时所得到的 50% 填充的结果。  这与 nbtsort.c 为新创建的树产生的结果相同。  注意，叶子页面和非叶子页面使用不同的 fillfactor。  还要注意，有一些进一步的特殊情况，其中 fillfactor 不以标准方式应用。
 *
 * 我们传入新元组的预定插入位置，表示为必须在其前面的元组的 offsetnumber（如果元组要放在末尾，则可以是 maxoff+1）。  新元组本身也被传入，因为它需要用于衡量后缀截断的有效性。  实现选择最大化后缀截断有效性的拆分点，来自一个小列表的替代候选拆分点，这些点将拆分的每一侧留有大致相同的自由空间份额。  后缀截断在平衡自由空间时是次要的，除了在具有大量重复元素的情况下。  注意，始终假设调用者会执行截断，即使在 pg_upgrade 的索引中实际上并非如此（！heapkeyspace 索引）。  请参阅 nbtree/README 以获取有关后缀截断的更多信息。
 *
 * 我们返回应该放在右侧页面的第一个现有元组的索引（称为 firstrightoff），加上一布尔值，用于指示新元组是放在左侧页面还是右侧页面。  你可以将返回的状态视为位于两个相邻数据项（左侧和 firstright 数据项）之间的一个点，在一个虚构的 origpage 版本中，该版本已经包含了 newitem。  这个布尔值是必需的，以便消除 firstrightoff == newitemoff 的情况下的歧义（即，有时需要确定拆分的 firstright 元组是否是 newitem，而不是 origpage 中 offset firstrightoff 的元组）。
 */
OffsetNumber _bt_findsplitloc(Relation fc_rel,
				 Page fc_origpage,
				 OffsetNumber fc_newitemoff,
				 Size fc_newitemsz,
				 IndexTuple fc_newitem,
				 bool *fc_newitemonleft)
{
	BTPageOpaque fc_opaque;
	int			fc_leftspace,
				fc_rightspace,
				fc_olddataitemstotal,
				fc_olddataitemstoleft,
				fc_perfectpenalty,
				fc_leaffillfactor;
	FindSplitData fc_state;
	FindSplitStrat fc_strategy;
	ItemId		fc_itemid;
	OffsetNumber fc_offnum,
				fc_maxoff,
				fc_firstrightoff;
	double		fc_fillfactormult;
	bool		fc_usemult;
	SplitPoint	fc_leftpage,
				fc_rightpage;

	fc_opaque = BTPageGetOpaque(fc_origpage);
	fc_maxoff = PageGetMaxOffsetNumber(fc_origpage);

	/* B树页面上可用的总自由空间，在固定开销之后 */
	fc_leftspace = fc_rightspace =
		PageGetPageSize(fc_origpage) - SizeOfPageHeaderData -
		MAXALIGN(sizeof(BTPageOpaqueData));

	/* 右侧页面将具有与旧页面相同的高键 */
	if (!P_RIGHTMOST(fc_opaque))
	{
		fc_itemid = PageGetItemId(fc_origpage, P_HIKEY);
		fc_rightspace -= (int) (MAXALIGN(ItemIdGetLength(fc_itemid)) +
							 sizeof(ItemIdData));
	}

	/* 在实际扫描它们之前计算数据项中的总空间 */
	fc_olddataitemstotal = fc_rightspace - (int) PageGetExactFreeSpace(fc_origpage);
	fc_leaffillfactor = BTGetFillFactor(fc_rel);

	/* 传入的 newitemsz 是 MAXALIGNED 但不包括行指针 */
	fc_newitemsz += sizeof(ItemIdData);
	fc_state.rel = fc_rel;
	fc_state.origpage = fc_origpage;
	fc_state.newitem = fc_newitem;
	fc_state.newitemsz = fc_newitemsz;
	fc_state.is_leaf = P_ISLEAF(fc_opaque);
	fc_state.is_rightmost = P_RIGHTMOST(fc_opaque);
	fc_state.leftspace = fc_leftspace;
	fc_state.rightspace = fc_rightspace;
	fc_state.olddataitemstotal = fc_olddataitemstotal;
	fc_state.minfirstrightsz = SIZE_MAX;
	fc_state.newitemoff = fc_newitemoff;

	/* newitem 不能是一个发布列表项 */
	Assert(!BTreeTupleIsPosting(fc_newitem));

	/*
	 * nsplits 不应超过 maxoff，因为一旦您想象新项目已在原始页面上，候选拆分点的数量至多与元组之间的点数相等（最终拆分数量可能稍低，因为并非所有元组之间的点都是合法的）。
	 */
	fc_state.maxsplits = fc_maxoff;
	fc_state.splits = palloc(sizeof(SplitPoint) * fc_state.maxsplits);
	fc_state.nsplits = 0;

	/*
	 * 扫描数据项并计算在每个可能位置拆分的空间使用情况
	 */
	fc_olddataitemstoleft = 0;

	for (fc_offnum = P_FIRSTDATAKEY(fc_opaque);
		 fc_offnum <= fc_maxoff;
		 fc_offnum = OffsetNumberNext(fc_offnum))
	{
		Size		fc_itemsz;

		fc_itemid = PageGetItemId(fc_origpage, fc_offnum);
		fc_itemsz = MAXALIGN(ItemIdGetLength(fc_itemid)) + sizeof(ItemIdData);

		/*
		 * 当项目偏移量不是 newitemoff 时，拆分的任一侧都不能是 newitem。
		 * 记录在原始页面上前一个数据项之后的拆分，但在原始页面上当前数据项之前。 (_bt_recsplitloc() 会在没有前一个项时拒绝拆分，这是我们依赖的。)
		 */
		if (fc_offnum < fc_newitemoff)
			fc__bt_recsplitloc(&fc_state, fc_offnum, false, fc_olddataitemstoleft, fc_itemsz);
		else if (fc_offnum > fc_newitemoff)
			fc__bt_recsplitloc(&fc_state, fc_offnum, true, fc_olddataitemstoleft, fc_itemsz);
		else
		{
			/*
			 * 在所有 "offnum < newitemoff" 的原始页面数据项之后记录拆分，但在 newitem 之前
			 */
			fc__bt_recsplitloc(&fc_state, fc_offnum, false, fc_olddataitemstoleft, fc_itemsz);

			/*
			 * 在 newitem 之后记录拆分，但在原始页面中偏移量为 newitemoff/当前偏移量的数据项之前
			 */
			fc__bt_recsplitloc(&fc_state, fc_offnum, true, fc_olddataitemstoleft, fc_itemsz);
		}

		fc_olddataitemstoleft += fc_itemsz;
	}

	/*
	 * 在所有原始页面数据项之后记录拆分，但在 newitem 之前。
	 * （不过仅在可能使 newitem 最终单独留在新右页的情况下。）
	 */
	Assert(fc_olddataitemstoleft == fc_olddataitemstotal);
	if (fc_newitemoff > fc_maxoff)
		fc__bt_recsplitloc(&fc_state, fc_newitemoff, false, fc_olddataitemstotal, 0);

	/*
	 * 我相信不可能找不到可行的拆分，但以防万一 ...
	 */
	if (fc_state.nsplits == 0)
		elog(ERROR, "could not find a feasible split point for index \"%s\"",
			 RelationGetRelationName(fc_rel));

	/*
	 * 开始在合法拆分点列表中搜索拆分点。最初给予每个拆分的一半可用空闲空间均衡化的主要考虑（从默认策略开始），同时在适当情况下应用最右侧和在新项后拆分的优化。
	 * 在原始/空间优化拆分点周围存在大量重复项的情况下，可能需要其他两种后备策略中的任一种。
	 *
	 * 默认策略在决定叶页面的拆分点时对后缀截断给予了一定的权重。它试图选择一个拆分点，在该拆分的左侧，新高键中的一个区分属性更早出现，从而最大化可以被截断的尾随属性的数量。只考虑那些暗示每侧可用空闲空间平衡的候选拆分点。请参见 _bt_defaultinterval()。
	 */
	if (!fc_state.is_leaf)
	{
		/* fillfactormult 仅在最右页面上使用 */
		fc_usemult = fc_state.is_rightmost;
		fc_fillfactormult = BTREE_NONLEAF_FILLFACTOR / 100.0;
	}
	else if (fc_state.is_rightmost)
	{
		/* 最右叶页面 -- fillfactormult 始终使用 */
		fc_usemult = true;
		fc_fillfactormult = fc_leaffillfactor / 100.0;
	}
	else if (fc__bt_afternewitemoff(&fc_state, fc_maxoff, fc_leaffillfactor, &fc_usemult))
	{
		/*
		 * 新项插入在叶页面上局部分组中的最右点 -- 应用 "在新项后拆分" 优化，或者通过应用叶填充因子的乘数，或选择精准的拆分点使 newitem 作为 lastleft。（usemult 已为我们设置。）
		 */
		if (fc_usemult)
		{
			/* fillfactormult 应根据叶填充因子设置 */
			fc_fillfactormult = fc_leaffillfactor / 100.0;
		}
		else
		{
			/* 找到 newitemoff 之后的精确拆分点 */
			for (int fc_i = 0; fc_i < fc_state.nsplits; fc_i++)
			{
				SplitPoint *fc_split = fc_state.splits + fc_i;

				if (fc_split->newitemonleft &&
					fc_newitemoff == fc_split->firstrightoff)
				{
					pfree(fc_state.splits);
					*fc_newitemonleft = true;
					return fc_newitemoff;
				}
			}

			/*
			 * 无法合法地在 newitemoff 之后拆分；在不使用填充因子乘数的情况下继续拆分。这是防御性的，在实践中永远不应需要。
			 */
			fc_fillfactormult = 0.50;
		}
	}
	else
	{
		/* 其他叶子页面。50:50页面分裂。 */
		fc_usemult = false;
		/* fillfactormult未使用，但要保持整洁 */
		fc_fillfactormult = 0.50;
	}

	/*
	 * 在原始顺序丢失之前，为页面保存最左和最右的分割
	 * 通过delta/fillfactormult排序。
	 */
	fc_leftpage = fc_state.splits[0];
	fc_rightpage = fc_state.splits[fc_state.nsplits - 1];

	/* 给分割点一个fillfactormult-wise的delta，并按delta排序 */
	fc__bt_deltasortsplits(&fc_state, fc_fillfactormult, fc_usemult);

	/* 确定默认策略的分割区间 */
	fc_state.interval = fc__bt_defaultinterval(&fc_state);

	/*
	 * 确定默认策略/分割区间是否会产生
	 * 足够区分的分割，或者我们是否应该更改策略。
	 * 替代策略改变被认为可接受的分割点范围
	 * （分割区间），并可能改变
	 * fillfactormult，以优雅地处理具有大量
	 * 重复项的页面。
	 *
	 * 为整个页面传递低分割和高分割（实际上，它们是为了一个
	 * 包含newitem的假想页面）。这些在初始分割
	 * 区间包含充满重复的分割点时使用，
	 * 我们需要考虑是否甚至有可能避免
	 * 附加一个堆TID。
	 */
	fc_perfectpenalty = fc__bt_strategy(&fc_state, &fc_leftpage, &fc_rightpage, &fc_strategy);

	if (fc_strategy == SPLIT_DEFAULT)
	{
		/*
		 * 默认策略已制定（始终在内部页面上奏效）。
		 * 原始分割区间仍然有效。
		 */
	}

	/*
	 * 当堆TID将被附加，但页面并不完全充满逻辑重复项时，
	 * 使用许多重复项策略。
	 *
	 * 分割区间扩大以包括所有合法候选分割
	 * 点。整个页面的分割区间中可能仅有两种不同值，
	 * 尽管页面上的大多数值也可能是唯一的。
	 * 最终的分割点将位于包含第一个/最优delta分割点的
	 * 重复元组组的左侧或右侧（设置了完美惩罚，以便
	 * 选择避免附加堆TID的最低delta分割点）。
	 * 最大化可以被截断的属性数量不是许多
	 * 重复项策略的目标。
	 *
	 * 单一值策略在无法避免附加
	 * 堆TID时使用。它安排将左侧页面留得非常满。
	 * 这在具有相同属性值的元组跨越多个页面的情况下
	 * 最大化空间利用率。新插入的重复项将倾向于
	 * 具有更高的堆TID值，因此我们将始终向右
	 * 进行分割。（单一值策略对!heapkeyspace索引
	 * 虽然没有特别有用，但并无害。）
	 */
	else if (fc_strategy == SPLIT_MANY_DUPLICATES)
	{
		Assert(fc_state.is_leaf);
		/* 不应尝试截断额外的用户属性 */
		Assert(fc_perfectpenalty ==
			   IndexRelationGetNumberOfKeyAttributes(fc_state.rel));
		/* 无需重新排序分割 - fillfactormult/deltas无变化 */
		fc_state.interval = fc_state.nsplits;
	}
	else if (fc_strategy == SPLIT_SINGLE_VALUE)
	{
		Assert(fc_state.is_leaf);
		/* 在页面末尾附近分割 */
		fc_usemult = true;
		fc_fillfactormult = BTREE_SINGLEVAL_FILLFACTOR / 100.0;
		/* 使用新的delta重新排序分割点 */
		fc__bt_deltasortsplits(&fc_state, fc_fillfactormult, fc_usemult);
		/* 附加一个堆TID是不可避免的，因此区间为1是可以的 */
		fc_state.interval = 1;
	}

	/* 
 * 在可接受的分割点中搜索（使用最终分割区间）具有最低惩罚的条目，因此预计能最大化扇出。为我们设置 *newitemonleft。
 */
	fc_firstrightoff = fc__bt_bestsplitloc(&fc_state, fc_perfectpenalty, fc_newitemonleft,
									 fc_strategy);
	pfree(fc_state.splits);

	return fc_firstrightoff;
}

/* 
 * 子例程，用于在页面上记录两个元组之间的特定点（可能是新项），即 *state 中 firstrightoff 和 newitemonleft 设置的组合，以供后续分析。这也是检查分割是否合法的一个方便点（如果不合法，将不会被记录）。
 *
 * firstrightoff 是原始页面上第一个移动到右页面的项目的偏移量，firstrightofforigpagetuplesz 是该元组的大小。在这种情况下，firstrightoff 可以大于最大偏移量，这意味着所有旧项目都会移到左页面，只有新项目移到右页面。在这种情况下，我们实际上并不使用 firstrightofforigpagetuplesz（实际上，我们在 firstright 元组恰好是 newitem 的任何分割中都不使用它）。
 *
 * olddataitemstoleft 是记录在此处的、合法的情况下分割点左侧所有旧项目的总大小。应不包括 newitemsz，因为它在此处处理。
 */
static void fc__bt_recsplitloc(FindSplitData *fc_state,
				OffsetNumber fc_firstrightoff,
				bool fc_newitemonleft,
				int fc_olddataitemstoleft,
				Size fc_firstrightofforigpagetuplesz)
{
	int16		fc_leftfree,
				fc_rightfree;
	Size		fc_firstrightsz;
	Size		fc_postingsz = 0;
	bool		fc_newitemisfirstright;

	/* 新项将成为分割点的 firstright 元组吗？ */
	fc_newitemisfirstright = (fc_firstrightoff == fc_state->newitemoff &&
						   !fc_newitemonleft);

	if (fc_newitemisfirstright)
		fc_firstrightsz = fc_state->newitemsz;
	else
	{
		fc_firstrightsz = fc_firstrightofforigpagetuplesz;

		/* 
		 * 当 firstright 元组是发布列表元组时计算后缀截断节省空间，只有在元组超过 64 字节（包括行指针开销，任意）时才进行。这避免了在其发布列表必须非常小的情况下访问元组（如果元组有一个的话）。
		 *
		 * 注意：如果 firstright 元组是 newitem，我们不这样做，因为 newitem 不能有发布列表。
 */
		if (fc_state->is_leaf && fc_firstrightsz > 64)
		{
			ItemId		fc_itemid;
			IndexTuple	fc_newhighkey;

			fc_itemid = PageGetItemId(fc_state->origpage, fc_firstrightoff);
			fc_newhighkey = (IndexTuple) PageGetItem(fc_state->origpage, fc_itemid);

			if (BTreeTupleIsPosting(fc_newhighkey))
				fc_postingsz = IndexTupleSize(fc_newhighkey) -
					BTreeTupleGetPostingOffset(fc_newhighkey);
		}
	}

	/* 记账所有旧元组 */
	fc_leftfree = fc_state->leftspace - fc_olddataitemstoleft;
	fc_rightfree = fc_state->rightspace -
		(fc_state->olddataitemstotal - fc_olddataitemstoleft);

	/*
	 * 右页上的第一个项变成左页的高键；
	 * 因此，它要计入左侧空间和右侧空间（我们不能假设后缀截断会使其变小）。当
	 * 索引包含属性时，左页高键的那些属性将被截断，从而使该页面有稍微更多的空闲空间。
	 * 然而，这不应该影响我们找到有效分割位置的能力，因为我们在左半边的空闲
	 * 空间上采取悲观的态度。此外，即使发生非 TID 属性的后缀截断，新高键通常也不会
	 * 比其依赖的第一个右元组小一个单一的 MAXALIGN() 量子。
	 *
	 * 如果我们处于叶子级别，假设在叶子级别拆分时，后缀截断无法避免
	 * 向左半边的新高键添加一个堆 TID。在实践中，新高键通常会更小，
	 * 并且很少会更大，但保守地假设最坏情况。我们确实会费心减去发布列表开销，
	 * 但仅当看起来会产生显著差异时。
	 * （发布列表是唯一的情况，在这种情况下，截断通常会使最终高键远小于第一个右键，
	 * 因此在那里更精确一点明显改善了空闲空间的平衡。）
	 */
	if (fc_state->is_leaf)
		fc_leftfree -= (int16) (fc_firstrightsz +
							 MAXALIGN(sizeof(ItemPointerData)) -
							 fc_postingsz);
	else
		fc_leftfree -= (int16) fc_firstrightsz;

	/* 考虑新项 */
	if (fc_newitemonleft)
		fc_leftfree -= (int16) fc_state->newitemsz;
	else
		fc_rightfree -= (int16) fc_state->newitemsz;

	/*
	 * 如果我们不在叶子级别，我们将能够丢弃最终位于右页上的第一个项的键数据。
	 */
	if (!fc_state->is_leaf)
		fc_rightfree += (int16) fc_firstrightsz -
			(int16) (MAXALIGN(sizeof(IndexTupleData)) + sizeof(ItemIdData));

	/* 如果合法则记录分割 */
	if (fc_leftfree >= 0 && fc_rightfree >= 0)
	{
		Assert(fc_state->nsplits < fc_state->maxsplits);

		/* 确定合法分割中最小的第一个右元组大小 */
		fc_state->minfirstrightsz = Min(fc_state->minfirstrightsz, fc_firstrightsz);

		fc_state->splits[fc_state->nsplits].curdelta = 0;
		fc_state->splits[fc_state->nsplits].leftfree = fc_leftfree;
		fc_state->splits[fc_state->nsplits].rightfree = fc_rightfree;
		fc_state->splits[fc_state->nsplits].firstrightoff = fc_firstrightoff;
		fc_state->splits[fc_state->nsplits].newitemonleft = fc_newitemonleft;
		fc_state->nsplits++;
	}
}

/*
 * 子程序根据当前填充因子将空间增量分配给物化数组中的候选分割点，并使用该填充因子对数组进行排序
 */
static void fc__bt_deltasortsplits(FindSplitData *fc_state, double fc_fillfactormult,
					bool fc_usemult)
{
	for (int fc_i = 0; fc_i < fc_state->nsplits; fc_i++)
	{
		SplitPoint *fc_split = fc_state->splits + fc_i;
		int16		fc_delta;

		if (fc_usemult)
			fc_delta = fc_fillfactormult * fc_split->leftfree -
				(1.0 - fc_fillfactormult) * fc_split->rightfree;
		else
			fc_delta = fc_split->leftfree - fc_split->rightfree;

		if (fc_delta < 0)
			fc_delta = -fc_delta;

		/* 保存增量 */
		fc_split->curdelta = fc_delta;
	}

	qsort(fc_state->splits, fc_state->nsplits, sizeof(SplitPoint), fc__bt_splitcmp);
}

/*
 * qsort 风格的比较器，由 _bt_deltasortsplits() 使用
 */
static int fc__bt_splitcmp(const void *fc_arg1, const void *fc_arg2)
{
	SplitPoint *fc_split1 = (SplitPoint *) fc_arg1;
	SplitPoint *fc_split2 = (SplitPoint *) fc_arg2;

	if (fc_split1->curdelta > fc_split2->curdelta)
		return 1;
	if (fc_split1->curdelta < fc_split2->curdelta)
		return -1;

	return 0;
}

/*
 * 子例程用于确定非最右叶页面是否应立即在
 * 新/到达元组的原始页面偏移量后进行拆分（或者在新项位于
 * 原始页面右侧时应应用叶填充因子）。当出现在复合索引中
 * 的局部单调递增插入模式存在时，这种做法是合适的，其中前导
 * 属性值形成局部分组，并且我们预期在不久的将来会对同一/当前
 * 分组（新项的分组）进行进一步插入。这可以被视为在最右叶
 * 页面拆分期间应用叶填充因子的变体，因为受益的情况将
 * 随着时间的推移趋于将叶页面填充到leaf fillfactor%的满度。
 *
 * 如果该分组最终没有未来的插入使用该空闲空间，我们可能会
 * 在一个“最显著列”元组分组的最右页面上留下额外的自由空间。
 * 这种影响是自我限制的；未来成为受影响分组的“右侧最近”
 * 分组的通常会充分利用额外的自由空间。
 *
 * 当例程返回true时，调用者使用优化，尽管调用者采取的
 * 确切操作有所不同。调用者以标准方式使用原始叶页面
 * 填充因子，而不是直接使用新的项偏移量，当*usemult
 * 在这里也被设置为true时。否则，调用者通过定位使得新
 * 元组成为拆分的lastleft元组的合法拆分点来应用优化。
 */
static bool fc__bt_afternewitemoff(FindSplitData *fc_state, OffsetNumber fc_maxoff,
					int fc_leaffillfactor, bool *fc_usemult)
{
	int16		fc_nkeyatts;
	ItemId		fc_itemid;
	IndexTuple	fc_tup;
	int			fc_keepnatts;

	Assert(fc_state->is_leaf && !fc_state->is_rightmost);

	fc_nkeyatts = IndexRelationGetNumberOfKeyAttributes(fc_state->rel);

	/* 单键索引在此不考虑 */
	if (fc_nkeyatts == 1)
		return false;

	/* 当新项为第一个时，无法推断出上升插入模式 */
	if (fc_state->newitemoff == P_FIRSTKEY)
		return false;

	/*
	 * 只在具有相同大小元组的页面上应用优化，因为序数
	 * 键很可能是固定宽度的。直接测试新元组是否
	 * 可变宽度也可能有效，但这样做无法将优化应用于具有
	 * numeric_ops属性的索引。
	 *
	 * 当新项的宽度与遍历页面时观察到的最小项相同时，推断
	 * 页面具有相同大小的元组，并且其他非支点元组的宽度
	 * 也必须相同。（请注意，可能被截断的现有高键未在
	 * olddataitemstotal中计算，必须从maxoff中减去。）
	 */
	if (fc_state->newitemsz != fc_state->minfirstrightsz)
		return false;
	if (fc_state->newitemsz * (fc_maxoff - 1) != fc_state->olddataitemstotal)
		return false;

	/*
	 * 避免在元组宽度大于由两个非NULL int8/int64属性
	 * （或四个非NULL int4/int32属性）组成的元组时应用优化
	 */
	if (fc_state->newitemsz >
		MAXALIGN(sizeof(IndexTupleData) + sizeof(int64) * 2) +
		sizeof(ItemIdData))
		return false;

	/*
	 * 最少第一个属性的值必须等于先前元组中对应
	 * 值以应用优化。新项也不能是重复的。
	 *
	 * 处理新项位于现有页面上所有项的右侧的情况。
	 * 这本身暗示着单调递增插入，因此这里不应用
	 * “堆TID邻接”测试。
	 */
	if (fc_state->newitemoff > fc_maxoff)
	{
		fc_itemid = PageGetItemId(fc_state->origpage, fc_maxoff);
		fc_tup = (IndexTuple) PageGetItem(fc_state->origpage, fc_itemid);
		fc_keepnatts = _bt_keep_natts_fast(fc_state->rel, fc_tup, fc_state->newitem);

		if (fc_keepnatts > 1 && fc_keepnatts <= fc_nkeyatts)
		{
			*fc_usemult = true;
			return true;
		}

		return false;
	}

	/*
	 * “低基数领先列，高基数后缀列”
	 * 具有随机插入模式的索引（例如，具有布尔列的索引，如
	 * 在“(book_is_in_print, book_isbn)”上的索引）为我们提供了
	 * 持续错误应用优化的风险。我们愿意接受非常偶尔的优化错误，
	 * 前提是我们出错的情况是稀少且自我限制的。
	 *
	 * 堆 TID 邻接性强烈暗示左侧的项是非常近期插入的，
	 * 这限制了优化的过度应用。此外，此处触发的所有不当情况
	 * 平均仍会在页面中间进行拆分。
	 */
	fc_itemid = PageGetItemId(fc_state->origpage, OffsetNumberPrev(fc_state->newitemoff));
	fc_tup = (IndexTuple) PageGetItem(fc_state->origpage, fc_itemid);
	/* 首先进行更便宜的测试 */
	if (BTreeTupleIsPosting(fc_tup) ||
		!fc__bt_adjacenthtid(&fc_tup->t_tid, &fc_state->newitem->t_tid))
		return false;
	/* 也检查与最右侧项情况相同的条件 */
	fc_keepnatts = _bt_keep_natts_fast(fc_state->rel, fc_tup, fc_state->newitem);

	if (fc_keepnatts > 1 && fc_keepnatts <= fc_nkeyatts)
	{
		double		fc_interp = (double) fc_state->newitemoff / ((double) fc_maxoff + 1);
		double		fc_leaffillfactormult = (double) fc_leaffillfactor / 100.0;

		/*
		 * 不允许调用者在新项之后拆分，因为这将导致拆分点
		 * 位于叶节点 fillfactor 拆分将使用的点的右侧 --
		 * 让调用者应用叶节点 fillfactor。
		 */
		*fc_usemult = fc_interp > fc_leaffillfactormult;

		return true;
	}

	return false;
}

/*
 * 确定两个堆 TID 是否“邻接”的子程序。
 *
 * 邻接意味着高 TID 很可能是在低 TID 后立即插入到
 * 堆关系中，可能是在当前事务中。
 */
static bool fc__bt_adjacenthtid(ItemPointer fc_lowhtid, ItemPointer fc_highhtid)
{
	BlockNumber fc_lowblk,
				fc_highblk;

	fc_lowblk = ItemPointerGetBlockNumber(fc_lowhtid);
	fc_highblk = ItemPointerGetBlockNumber(fc_highhtid);

	/* 当堆块匹配时，做出乐观的邻接假设 */
	if (fc_lowblk == fc_highblk)
		return true;

	/* 当堆块一个向上时，第二个偏移应为 FirstOffsetNumber */
	if (fc_lowblk + 1 == fc_highblk &&
		ItemPointerGetOffsetNumber(fc_highhtid) == FirstOffsetNumber)
		return true;

	return false;
}

/*
 * 找到候选拆分点中“最佳”拆分点的子程序。
 * 最佳拆分点是当前/最终拆分区间内具有最低惩罚的拆分点。
 * 惩罚是一个抽象评分，其定义因我们是在拆分叶页面
 * 还是内部页面而异。有关详细信息，请参阅 _bt_split_penalty()。
 *
 * “perfectpenalty”被假定为候选拆分点中可能的最低惩罚。
 * 这使我们能够提前返回，而不浪费周期计算所有候选
 * 拆分的第一个不同属性，当这显然无法改善我们的选择
 * （或者当我们只想要一个最小区分的拆分点，不想让
 * 拆分变得不平衡）。
 *
 * 我们返回应放在右侧页面的第一个现存元组的索引，
 * 以及一个布尔值，指示新项是否位于拆分点的左侧。
 */
static OffsetNumber fc__bt_bestsplitloc(FindSplitData *fc_state, int fc_perfectpenalty,
				 bool *fc_newitemonleft, FindSplitStrat fc_strategy)
{
	int			fc_bestpenalty,
				fc_lowsplit;
	int			fc_highsplit = Min(fc_state->interval, fc_state->nsplits);
	SplitPoint *fc_final;

	fc_bestpenalty = INT_MAX;
	fc_lowsplit = 0;
	for (int fc_i = fc_lowsplit; fc_i < fc_highsplit; fc_i++)
	{
		int			fc_penalty;

		fc_penalty = fc__bt_split_penalty(fc_state, fc_state->splits + fc_i);

		if (fc_penalty < fc_bestpenalty)
		{
			fc_bestpenalty = fc_penalty;
			fc_lowsplit = fc_i;
		}

		if (fc_penalty <= fc_perfectpenalty)
			break;
	}

	fc_final = &fc_state->splits[fc_lowsplit];

	/*
	 * 存在“多个重复”策略在一大组重复项右侧进行单调递减插入时反复执行错误操作的风险。重复分裂可能会留下一个个右半页，其中的空闲空间永远无法使用。这必须避免。
	 *
	 * 考虑一个几乎被NULL填满的单整数属性NULLS FIRST索引中最左侧页面的例子。单调递减的整数插入可能导致同一个最左侧页面在同一点上重复分裂。每次分裂都将其新高键从大量NULLs右侧的最低当前值派生，这个值将永远高于所有未来的整数插入，导致所有未来的整数插入都指向同一个最左侧页面。
	 */
	if (fc_strategy == SPLIT_MANY_DUPLICATES && !fc_state->is_rightmost &&
		!fc_final->newitemonleft && fc_final->firstrightoff >= fc_state->newitemoff &&
		fc_final->firstrightoff < fc_state->newitemoff + 9)
	{
		/*
		 * 通过在新项目恰好位于“多个重复”分裂点的右侧时执行50:50分裂来避免该问题。
		 * （注意，用于测试插入是否“恰好在右侧”的分裂点的测试是保守的。）
		 */
		fc_final = &fc_state->splits[0];
	}

	*fc_newitemonleft = fc_final->newitemonleft;
	return fc_final->firstrightoff;
}

#define LEAF_SPLIT_DISTANCE			0.050
#define INTERNAL_SPLIT_DISTANCE		0.075

/*
 * 返回一个用于默认策略的分裂区间。这是对候选分裂点数量的限制，以便进行进一步考虑。只有一部分候选分裂点（即位于当前已排序的分裂数组开头的那些）落在分裂区间内。分裂区间在_bt_bestsplitloc()中应用。
 *
 * 分裂区间表示可以接受的分裂点范围——那些具有可接受平衡的leftfree和rightfree值。最终选择的分裂点是在此分裂区间内具有最低“惩罚”的分裂点（除非我们更改整个策略，在这种情况下区间也会变化——参见_bt_strategy()）。
 *
 * “前缀B树”论文将叶子分裂的分裂区间称为sigma l，将内部（“分支”）分裂称为sigma b。虽然很难为分裂区间的大小提供理论依据，但显然较小的分裂区间可以使L+1级的元组平均变得更小，而不会明显影响L级的空间利用率。
 * （注意，如果对后缀截断的处理被教导为在诸如文本等数据类型的最后一个属性/数据中“内截”元组，则我们计算分裂区间的方式可能需要更改，这在论文中基本上是如何假设其工作的。）
 */
static int fc__bt_defaultinterval(FindSplitData *fc_state)
{
	SplitPoint *fc_spaceoptimal;
	int16		fc_tolerance,
				fc_lowleftfree,
				fc_lowrightfree,
				fc_highleftfree,
				fc_highrightfree;

	/*
	 * 确定比我们愿意容忍的更高和更低的leftfree和rightfree值。请注意，在所有非主轴元组（数据项）来自一个叶子页面且尺寸一致的常见情况下，最终的分裂区间将大约是nsplits的10%。在分裂内部页面时，我们会更具攻击性。
	 */
	if (fc_state->is_leaf)
		fc_tolerance = fc_state->olddataitemstotal * LEAF_SPLIT_DISTANCE;
	else
		fc_tolerance = fc_state->olddataitemstotal * INTERNAL_SPLIT_DISTANCE;

	/* 第一个候选分裂点是最均衡的 */
	fc_spaceoptimal = fc_state->splits;
	fc_lowleftfree = fc_spaceoptimal->leftfree - fc_tolerance;
	fc_lowrightfree = fc_spaceoptimal->rightfree - fc_tolerance;
	fc_highleftfree = fc_spaceoptimal->leftfree + fc_tolerance;
	fc_highrightfree = fc_spaceoptimal->rightfree + fc_tolerance;

	/*
	 * 遍历拆分点，从“spaceoptimal”之后的拆分开始。找到第一个将自由空间划分得如此不均匀的拆分点，包含它在拆分区间将是不可接受的。
	 */
	for (int fc_i = 1; fc_i < fc_state->nsplits; fc_i++)
	{
		SplitPoint *fc_split = fc_state->splits + fc_i;

		/* 此处不能使用curdelta，因为它的值通常是加权的 */
		if (fc_split->leftfree < fc_lowleftfree || fc_split->rightfree < fc_lowrightfree ||
			fc_split->leftfree > fc_highleftfree || fc_split->rightfree > fc_highrightfree)
			return fc_i;
	}

	return fc_state->nsplits;
}

/*
 * 子程序决定拆分是否应该使用默认策略/初始拆分区间，或者是否应该使用替代策略完成页面拆分（这仅在叶页面上可行）。
 *
 * 调用者基于此处*strategy的设置使用替代策略（或坚持默认策略）。返回值是“完美惩罚”，它被传递给_bt_bestsplitloc()作为调用者愿意去避免在使用许多重复策略时附加堆TID的最终约束（它还节省了_bt_bestsplitloc()的不必要周期）。
 */
static int fc__bt_strategy(FindSplitData *fc_state, SplitPoint *fc_leftpage,
			 SplitPoint *fc_rightpage, FindSplitStrat *fc_strategy)
{
	IndexTuple	fc_leftmost,
				fc_rightmost;
	SplitPoint *fc_leftinterval,
			   *fc_rightinterval;
	int			fc_perfectpenalty;
	int			fc_indnkeyatts = IndexRelationGetNumberOfKeyAttributes(fc_state->rel);

	/* 假设目前不会使用替代策略 */
	*fc_strategy = SPLIT_DEFAULT;

	/*
	 * 使用整个页面（实际上，包含新项的整个虚拟页面）观察到的最小firstright项大小作为内部页面的完美惩罚。这可以在大多数或所有拆分（不仅仅是区间内的拆分）具有相同大小的firstright元组的常见情况下节省周期。
	 */
	if (!fc_state->is_leaf)
		return fc_state->minfirstrightsz;

	/*
	 * 使用当前拆分区间中最左和最右拆分的最左和最右元组
	 */
	fc__bt_interval_edges(fc_state, &fc_leftinterval, &fc_rightinterval);
	fc_leftmost = fc__bt_split_lastleft(fc_state, fc_leftinterval);
	fc_rightmost = fc__bt_split_firstright(fc_state, fc_rightinterval);

	/*
	 * 如果初始拆分区间可以产生一个拆分点，至少可以避免在新高键中附加堆TID，那么我们完成了。使用默认策略和初始拆分区间完成拆分。
	 */
	fc_perfectpenalty = _bt_keep_natts_fast(fc_state->rel, fc_leftmost, fc_rightmost);
	if (fc_perfectpenalty <= fc_indnkeyatts)
		return fc_perfectpenalty;

	/*
	 * 计算当即使是他们的“完美”惩罚对初始/默认拆分区间表明该区间甚至不包含一个避免附加堆TID的拆分时调用者应该如何完成拆分。
	 *
	 * 使用最左拆分的lastleft元组和最右拆分的firstright元组来评估每一个可能的拆分。
	 */
	fc_leftmost = fc__bt_split_lastleft(fc_state, fc_leftpage);
	fc_rightmost = fc__bt_split_firstright(fc_state, fc_rightpage);

	/*
	 * 如果页面（包括新项）有许多重复项但并不完全由重复项填满，则将执行许多重复策略拆分。如果页面完全由重复项填满，则将执行单值策略拆分。
	 */
	fc_perfectpenalty = _bt_keep_natts_fast(fc_state->rel, fc_leftmost, fc_rightmost);
	if (fc_perfectpenalty <= fc_indnkeyatts)
	{
		*fc_strategy = SPLIT_MANY_DUPLICATES;

		/*
		 * 许多重复策略应在围绕delta-optimal拆分点的重复项组的任一侧进行拆分。返回indnkeyatts而不是真正的完美惩罚以实现这一点。（如果此处返回完美惩罚，则低基数复合索引可能会有持续的不平衡拆分。）
		 *
		 * 请注意，调用者在极少数情况下不会进行许多重复的拆分，当在拆分点的立即右侧似乎有不断减少的插入时。这必须在做出最终决定之前发生，在_bt_bestsplitloc()中。
		 */
		return fc_indnkeyatts;
	}

	/*
	 * 单值策略仅适用于不断增加的堆
	 * TIDs；否则，原始默认策略拆分应继续进行，以
	 * 避免病态性能。使用页面高键推断这是否是存储相同重复值的
	 * 页面的最右页面。这不应阻止稍微错序的堆 TIDs 的插入
	 * 使用单值策略，因为这是在同一重复值的并发插入者中
	 * 预期的情况。
	 */
	else if (fc_state->is_rightmost)
		*fc_strategy = SPLIT_SINGLE_VALUE;
	else
	{
		ItemId		fc_itemid;
		IndexTuple	fc_hikey;

		fc_itemid = PageGetItemId(fc_state->origpage, P_HIKEY);
		fc_hikey = (IndexTuple) PageGetItem(fc_state->origpage, fc_itemid);
		fc_perfectpenalty = _bt_keep_natts_fast(fc_state->rel, fc_hikey,
											 fc_state->newitem);
		if (fc_perfectpenalty <= fc_indnkeyatts)
			*fc_strategy = SPLIT_SINGLE_VALUE;
		else
		{
			/*
			 * 让调用者使用默认策略完成拆分，因为页面
			 * 似乎不是填充该值的重复项的最右页面
			 */
		}
	}

	return fc_perfectpenalty;
}

/*
 * 子程序用于定位当前/默认
 * 拆分区间的最左和最右拆分。请注意，只有在区间内有一个
 * 拆分时，它将是相同的拆分。
 */
static void fc__bt_interval_edges(FindSplitData *fc_state, SplitPoint **fc_leftinterval,
				   SplitPoint **fc_rightinterval)
{
	int			fc_highsplit = Min(fc_state->interval, fc_state->nsplits);
	SplitPoint *fc_deltaoptimal;

	fc_deltaoptimal = fc_state->splits;
	*fc_leftinterval = NULL;
	*fc_rightinterval = NULL;

	/*
	 * Delta 是到最佳拆分点的绝对距离，因此
	 * 最左和最右拆分点通常将在数组的末尾
	 */
	for (int fc_i = fc_highsplit - 1; fc_i >= 0; fc_i--)
	{
		SplitPoint *fc_distant = fc_state->splits + fc_i;

		if (fc_distant->firstrightoff < fc_deltaoptimal->firstrightoff)
		{
			if (*fc_leftinterval == NULL)
				*fc_leftinterval = fc_distant;
		}
		else if (fc_distant->firstrightoff > fc_deltaoptimal->firstrightoff)
		{
			if (*fc_rightinterval == NULL)
				*fc_rightinterval = fc_distant;
		}
		else if (!fc_distant->newitemonleft && fc_deltaoptimal->newitemonleft)
		{
			/*
			 * "传入的元组将变为最右"（远）在
			 * "传入的元组将变为最左"（delta-optimal）的
			 * 左侧
			 */
			Assert(fc_distant->firstrightoff == fc_state->newitemoff);
			if (*fc_leftinterval == NULL)
				*fc_leftinterval = fc_distant;
		}
		else if (fc_distant->newitemonleft && !fc_deltaoptimal->newitemonleft)
		{
			/*
			 * "传入的元组将变为最左"（远）在
			 * "传入的元组将变为最右"（delta-optimal）的右侧
			 */
			Assert(fc_distant->firstrightoff == fc_state->newitemoff);
			if (*fc_rightinterval == NULL)
				*fc_rightinterval = fc_distant;
		}
		else
		{
			/* 在初始拆分区间中只有一或两个拆分 */
			Assert(fc_distant == fc_deltaoptimal);
			if (*fc_leftinterval == NULL)
				*fc_leftinterval = fc_distant;
			if (*fc_rightinterval == NULL)
				*fc_rightinterval = fc_distant;
		}

		if (*fc_leftinterval && *fc_rightinterval)
			return;
	}

	Assert(false);
}

/*
 * 子程序用于查找调用者的候选拆分点的惩罚。
 *
 * 在叶子页面上，惩罚是区分拆分两侧的属性编号。
 * 它是必须包含在左页面的新高键中的最后一个属性。
 * 在某些情况下，当堆 TID 需要在截断期间附加时，它可以
 * 大于键属性的数量。
 *
 * 在内部页面上，惩罚仅仅是拆分的最右元组的大小
 * （包括行指针开销）。这个元组将成为左页面的新高键。
 */
static inline int fc__bt_split_penalty(FindSplitData *fc_state, SplitPoint *fc_split)
{
	IndexTuple	fc_lastleft;
	IndexTuple	fc_firstright;

	if (!fc_state->is_leaf)
	{
		ItemId		fc_itemid;

		if (!fc_split->newitemonleft &&
			fc_split->firstrightoff == fc_state->newitemoff)
			return fc_state->newitemsz;

		fc_itemid = PageGetItemId(fc_state->origpage, fc_split->firstrightoff);

		return MAXALIGN(ItemIdGetLength(fc_itemid)) + sizeof(ItemIdData);
	}

	fc_lastleft = fc__bt_split_lastleft(fc_state, fc_split);
	fc_firstright = fc__bt_split_firstright(fc_state, fc_split);

	return _bt_keep_natts_fast(fc_state->rel, fc_lastleft, fc_firstright);
}

/*
 * 子程序用于获取拆分点的最后左侧 IndexTuple
 */
static inline IndexTuple fc__bt_split_lastleft(FindSplitData *fc_state, SplitPoint *fc_split)
{
	ItemId		fc_itemid;

	if (fc_split->newitemonleft && fc_split->firstrightoff == fc_state->newitemoff)
		return fc_state->newitem;

	fc_itemid = PageGetItemId(fc_state->origpage,
						   OffsetNumberPrev(fc_split->firstrightoff));
	return (IndexTuple) PageGetItem(fc_state->origpage, fc_itemid);
}

/*
 * 子程序用于获取拆分点的最右 IndexTuple
 */
static inline IndexTuple fc__bt_split_firstright(FindSplitData *fc_state, SplitPoint *fc_split)
{
	ItemId		fc_itemid;

	if (!fc_split->newitemonleft && fc_split->firstrightoff == fc_state->newitemoff)
		return fc_state->newitem;

	fc_itemid = PageGetItemId(fc_state->origpage, fc_split->firstrightoff);
	return (IndexTuple) PageGetItem(fc_state->origpage, fc_itemid);
}
